COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00014 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a49.tex[154,phy] \today\hfill}

\bigskip
\line{\bf Homorphisms\hfil}

Let $D$ be a domain, and $\oplus$ a function of two arguments on that domain,
customarily written between its arguments, as $x\oplus y$, and called
an {\sl operator}. If $(x\oplus y)\oplus z=x\oplus(y\oplus z)$ for
all~$x$, $y$, and~$z$, we say $\oplus$ is {\sl associative}. We can
write such sums as $x\oplus y\oplus z$ without parentheses. If there is
some $i\in D$ for which $i\oplus x=x=x\oplus i$ for all~$x$, we say that
$i$ is an {\sl identity\/} element of~$D$.

\medskip
\display 38pt::{\bf Drill:}
Show that there cannot be two different identity elements.

\medskip\noindent
A domain with an associative operator is called a {\sl semigroup\/}; if there
is an identity element, it is called a {\sl monoid}.

A monoid may be {\sl generated\/} from a particular subset: there is a
subset $G⊂D$, and each $x$ is $i\oplus g↓1\oplus g↓2\oplus\cdots\oplus g↓n$
for some $n≥0$, each $g↓j$ being in~$G$. The elements of~$G$ are called
{\sl generators}. If $G$ is finite, the monoid is {\sl finitely generated}.
A~semigroup is {\sl generated\/} by~$G$ if each~$x$ is $g↓1\oplus g↓2\oplus \cdots
\oplus g↓n$, $n≥1$.
If there is exactly one way to generate each element, the monoid is called
{\sl free}. Examples:

$$\vcenter{\halign{#\hfil\quad&\hfil#\hfil\quad&\hfil#\hfil\quad%
&\hfil#\hfil\quad&#\hfil\cr
Domain&Operator&Identity&Generators&Called\cr
\noalign{\smallskip}
Natural numbers, $N$&$+$&0&1&free monoid\cr
Positive integers, $N↑+$&$+$&none&1&free semigroup\cr
Positive integers, $N↑+$&$\times$&1&prime numbers&monoid\cr
$\Sigma↑{\ast}$&$\otimes$&$\epsilon$&$\Sigma$&free monoid\cr
$\Sigma↑+$&$\otimes$&none&$\Sigma$&free semigroup\cr
Functions on $S$&$\circ$ (composition)&$f(x)=x$&&monoid\cr
Relations on $S$&$\circ$&$I↓S$&&monoid\cr}}$$

\display 38pt::{\bf Drill:} Which of the above are finitely generated?

\medskip
Let $m$ be a free monoid generated by $G$, with identity {\bf 0} and
operator~$\oplus$. To prove that $p(x)$ for all $x\in G$, we can use
mathematical induction.

\medskip
\line{\qquad\qquad If $p(i)$, and if $p(x)⊃p(x\oplus g)$ for all $g\in G$,\hfill (1)}
\line{\qquad\qquad we may infer that $p(x)$ for all $x\in m$.\hfill}

\medskip\noindent
The fact that $m$ is free implies

\medskip
\line{\qquad\qquad $x\oplus g≠i$ if $g\in G$\hfill (2)}
\line{\qquad\qquad $x\oplus g↓1≠y\oplus g↓2$ if $g↓1,g↓2\in G$, unless
$x=y$ and $g↓1=g↓2$.\hfill (3)}

\medskip\noindent
Let $m'$ also be a monoid with identity {\bf 1} and operator $\odot$.
It need not be free. Take any function $f(g)=e↓g$ from $G$ to~$m'$.
There is a natural way to extend it into a function from~$m$ to~$m'$;
define:

\medskip
\line{\qquad\qquad $f({\bf 0})={\bf 1}$\hfill (4)}
\line{\qquad\qquad $f(x\oplus g)=f(x)\odot e↓g$ for $g\in G$.\hfill (5)}

\medskip\noindent
By induction, $f(x)$ is defined and unique for all $x\in m$. Such a function
is called a {\sl homomorphism}.

\medskip
\line{{\bf Theorem.}\xskip $f(g)=e↓g$.\hfill (6)}

\medskip\noindent
{\bf Proof.} Substitute {\bf 0} for $x$ in (5) and simplify.

\medskip
\line{{\bf Theorem.}\xskip $f(x\oplus y)=f(x)\odot f(y)$ \xskip 
{\sl (Distributivity)}.\hfill (7)}

\medskip\noindent
{\bf Proof.} 
\smallskip\noindent
Base step, $y={\bf 0}$.
$f(x\oplus {\bf 0})=f(x)$,
$f(x)\odot f({\bf 0})=f(x)\odot{\bf 1}=f(x)$.

\smallskip\noindent
Induction step, assuming $y=z\oplus g$, $f(x\oplus z)=f(x)\odot f(z)$.
$f(x\oplus y)=f(x\oplus z\oplus g)=f(x\oplus z)\odot e↓g=
f(x)\odot f(z)\odot e↓g$,
$f(x)\odot f(y)=f(x)\odot f(z\oplus g)=f(x)\odot f(z)\odot e↓g$.
\quad\blackslug

\smallskip
A homomorphism is a natural way to extend a 
function that maps the generators of one monoid into another monoid,
 and is the only such extension that maps identities onto each other
and is distributive.

Examples of homomorphisms:

\medskip
\display 20pt:{$\bullet$}:
Let $m=\Sigma↑{\ast}$, $\oplus =\otimes$, ${\bf 0}=\epsilon$, $G=\Sigma$.

\medskip
\display 40pt:{$\bullet\bullet$}:
Length:
\display 40pt::
Let $m'=N$, $\odot =+$, ${\bf 1}=0$, $e↓g=1$.
Then $f(x)$ is the length $|x|$, and $|xy|=|x|+|y|$.

\medskip
\display 40pt:{$\bullet\bullet$}:
String-to-string homomorphism:
\display 40pt::
Let $m'=\Delta↑{\ast}$, $\odot =\otimes$, ${\bf 1}=\epsilon$, $e↓g$ arbitrary.
Then $f(x\otimes y)=f(x)\otimes f(y)$.

\medskip
\display 40pt:{$\bullet\bullet$}:
String to its transition relation for machine $M$:
\display 40pt::
Let $m'=2↑{Q\times Q}$, the set of relations on $Q=Q↓M$;
$\odot =\circ$; ${\bf 1}=I↓Q$; $f(x)=\delta↓x$.
Then $\delta↓{\epsilon}=I↓Q$, $\delta↓{xy}=\delta↓x\circ\delta↓y$.

\medskip
\display 40pt:{$\bullet\bullet$}:
String to its infix equivalence class $\Lap$, for some language $L$:
\display 40pt::
Let $m'=\{\,[x]\mid x\in\Sigma↑{\ast}\,\}$, the set of equivalence classes
of~$\Lap$;
$\odot$~is defined uniquely by $[x]\odot[y]=[xy]$; ${\bf 1}=[\epsilon]$;
$f(x)=[x]$.

\medskip
\display 40pt:{$\bullet\bullet$}:
String to (context-free) language homomorphism:
\display 40pt::
Let $m'=2↑{\Delta↑{\ast}}$, the set of languages over~$\Delta$; 
$\odot =\otimes$ (concatenation of languages, not strings); 
${\bf 1}=\{\epsilon\}$;
$e↓g$~an arbitrary (context-free) language over~$\Delta$. Then
$f(\epsilon)=\{\epsilon\}$, $f(x\otimes y)=f(x)\otimes f(y)$.
If $L$~is a language over~$\Sigma$, $\bigcup↓{x\in L}f(x)$ is what
H\&U call a {\sl substitution}. A~theorem states that if each~$e↓g$
is a CFL, and $L$ is a CFL, then $\bigcup↓{x\in L}f(x)$ is a CFL.

\medskip
{\bf Drill.} Prove the theorem.

\medskip
\display 20pt:{$\bullet$}:
Let $m=N$, $\oplus =+$, ${\bf 0}=0$, $G=\{1\}$.

\medskip
\display 40pt:{$\bullet\bullet$}:
Let $m'=N$, $\odot =+$, ${\bf 1}=0$, $e=e↓1$ arbitrary.
Then $f↓e(x)=e\times x$, and $f↓e(x+y)=f↓e(x)+f↓e(y)$; that is,
$e(x+y)=ex+ey$.

\medskip
\display 40pt:{$\bullet\bullet$}:
Define the equivalence relation modulo~$p$ as $x≡$ iff $p$ divides $x-y$.
$m'=\{[i]\}$, the set of equivalence classes into which $z$ is partitioned
by the equivalence relation. Let $f↓a(1)=[a]$.
Then $f↓a(x)=[ax]$, and $[a(x+y)]=[ax]+[ay]$.

\medskip
\display 20pt:{$\bullet$}:
Let $m'=(S→N)$, the set of functions from arbitrary set~$S$ into~$N$;
$\oplus =+$; ${\bf 0}=$ the identically zero function;
$G=\{\,g↓a\mid a\in S\,\}$ where $g↓a(a)=1$, $g↓a(x)=0$ otherwise.

\medskip
\display 40pt:{$\bullet\bullet$}:
Let $m'=N$, $\odot =+$, ${\bf 1}=0$, $e↓a=e↓{g↓a}$ arbitrary. Then
$f(x)$ is the inner product of~$x$ with a fixed function that maps~$a$
into~$e↓a$; $f(x+y)=f(x)+f(y)$.


\bigskip
\parindent0pt
\copyright 1986 Robert W. Floyd.
First draft (not published)
May 29, 1986.
%revised date;
%subsequently revised.

\bye